题意:交互题,三堆石子,石子个数分别为 ,选择先手或者后手进行游戏。先手给定一个数 ,后手将一堆石子个数增加 ,不能连续增加同一堆两次。如果有两堆石子个数一样,后手输;如果 次内先手没有赢,则后手赢。问谁有必胜策略。
首先,我们考虑什么时候后手会输。
假设此时 :
- 如果 ,则不论可以修改哪个,后手均不会输。
- 如果 ,此时如果不能修改 ,则可以构造出 使得后手必败;如果可以修改 ,则不能保证。
得出结论:当且仅当 成等差数列,且最大数不能被修改时后手败。
我们考虑是否能构造一种方法,使得在若干步后,三堆石子满足这一条件。
考虑如何能得到等差数列,且最大数不能修改?设原来三堆石子为 且 ,并且最大数不能被修改,那么就可以构造 满足条件。
为啥?假设修改 ,则三个数变为 ,即为 ,其中 ,符合上面的描述。修改 同理。
此时我们发现,中位数为 ,即原来的最大数;公差可以根据这一点推出:用 减去另一个没有变化的数。
问题转化为如何固定最大值不能动。我们一开始构造 ,即大于任何一个数的数,此时被修改的不管是哪个,都是修改后的最大值。记录这个最大值,然后按照上面说的做即可。
总结:首先构造 ,获得最大值位置,用指针记录。然后根据最大值,构造 ,其中 为这个最大值, 为三个数的和。最后得到一个最大数不能修改的等差数列,构造 为公差即可。
没错你没看错,先手在三步以内必胜。
代码:
//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e10;
ll a[3], *p, k, s;
ll interact(ll x) {
printf("%lld\n", x);
fflush(stdout);
ll res;
scanf("%lld", &res);
if(!res) exit(0);
a[--res] += x;
return res;
}
int main() {
scanf("%lld%lld%lld", &a[0], &a[1], &a[2]);
puts("First"); fflush(stdout);
s = a[0] + a[1] + a[2] + inf;
k = interact(inf);
p = &a[k];
k = interact((*p)*3-s);
ll _ = 3 - (p - a) - k;
k = interact((*p)-a[_]);
return 0;
}